Critical operational processes of businesses, governments, and institutions often rely on software applications that execute on distributed systems that communicate over networks (such as, Wide Area Networks (WANs) or Internet links). Proper performance of these applications is critical to continued operation of an enterprise's business processes and the productivity of employees. Disruptions to the network applications and business processes can be very costly, leading to lost employee productivity, lost revenue opportunities, and/or increased costs.
End-to-end performance—that is, the performance or response time measured between two hosts implementing a network application over a network—most closely represents the performance of a business process. Ideally, the performance of the network communication path between the two ends of a network application should be seamless. Indeed, one-way or round trip delay guarantees are often an integral part of service level agreement (SLA) specifications. In addition, for some network applications such as VoIP, the amount of network delay, in one or both directions along a communications path, may determine whether the data flows traversing a network can support mission-critical applications, or be of minimal to no use.
Generally, network delay may incorporate some or all of the following basic components—propagation, serialization, packetization and queuing delays. Propagation delay, based on the speed of light, is the time a signal spends in transit across a communications medium, such as a wire, cable or air. Serialization delay (also known as insertion delay) characterizes the time required to insert a signal corresponding to a packet on the communications medium. For example, the serialization delay or time to place one byte of information on a 64 Kbps circuit is 125 microseconds, while the serialization time required to place the same byte of information on an OC-3 circuit is 0.05 microseconds. Packetization delay is the delay associated with the process of collecting digital data for placement into the payload of a packet until enough samples are collected to fill the packet or cell payload. Queuing or buffering delay is the time a packet spends in the buffer of a node on the network while it waits on other packets to be serviced. Other related delays can relate to delays inherent to the network application, such as VoIP which also may include coding delay—the time to digitize and compress voice data signals.
Given a general understanding of the fixed and variable delay components and network application requirements, a delay budget can be calculated. The delay budget is the amount of delay permissible for a given network application implemented across the planned network while still meeting differentiated QoS objectives. For VoIP traffic, for example, the generally-accepted limit for good-quality voice connection delay is about 200 to 250 ms one-way. As delays rise over this amount, talkers and listeners become un-synchronized, rendering it difficult for call participants to determine whose turn it is to talk.
Given the importance of network application performance, a variety of technologies have been deployed to track delay metrics associated with computer networks and networked applications. Some network performance monitoring solutions rely on passive techniques (e.g., recording packet traces and arrival times), while others rely on active methods that inject synthetic traffic into the network. For example, co-pending and commonly owned U.S. patent application Ser. Nos. 09/710,442 and 10/812,198 disclose technologies that calculate the time traffic spends traveling between a client and a server and the time used by the server itself based on passive monitoring of packet arrival times at a network device deployed on a WAN link. Moreover, some network monitoring devices, such as the PacketShaper® network application traffic management device offered by Packeteer, Inc. of Cupertino, Calif., include synthetic transaction agents that inject synthetic traffic into the network to monitor network performance. Synthetic transaction agents are often deployed on carrier network equipment to track point-to-point service level agreements corresponding to a WAN circuit.
In addition, to facilitate monitoring, management and control of network environments, a variety of network devices, applications, technologies and services have been developed. For example, certain data flow rate control mechanisms have been developed to provide a means to control and optimize efficiency of data transfer as well as allocate available bandwidth among a variety of business enterprise functionalities. For example, U.S. Pat. No. 6,038,216 discloses a method for explicit data rate control in a packet-based network environment without data rate supervision. Data rate control directly moderates the rate of data transmission from a sending host, resulting in just-in-time data transmission to control inbound traffic and reduce the inefficiencies associated with dropped packets. Bandwidth management devices allow for explicit data rate control for flows associated with a particular traffic classification. For example, U.S. Pat. No. 6,412,000, above, discloses automatic classification of network traffic for use in connection with bandwidth allocation mechanisms. U.S. Pat. No. 6,046,980 discloses systems and methods allowing for application layer control of bandwidth utilization in packet-based computer networks. For example, bandwidth management devices allow network administrators to specify policies operative to control and/or prioritize the bandwidth allocated to individual data flows according to traffic classifications. In addition, certain bandwidth management devices, as well as certain routers, allow network administrators to specify aggregate bandwidth utilization controls to divide available bandwidth into partitions. With some network devices, these partitions can be configured to provide a minimum bandwidth guarantee, and/or cap bandwidth, as to a particular class of traffic. An administrator specifies a traffic class (such as FTP data, or data flows involving a specific user or network application) and the size of the reserved virtual link—i.e., minimum guaranteed bandwidth and/or maximum bandwidth. Such partitions can be applied on a per-application basis (protecting and/or capping bandwidth for all traffic associated with an application) or a per-user basis (controlling, prioritizing, protecting and/or capping bandwidth for a particular user). In addition, certain bandwidth management devices allow administrators to define a partition hierarchy by configuring one or more partitions dividing the access link and further dividing the parent partitions into one or more child partitions. U.S. patent application Ser. No. 10/108,085 discloses data structures and methods for implementing a partition hierarchy.
Relative to a given network device deployed to control or manage resource utilization of data flows traversing a communications path, a partition is essentially a bandwidth allocation and queuing mechanism. That is, after a packet processor classifies each packet and pushes each packet onto a partition queue associated with the appropriate partition, another process, typically, loops through the partition queues to pop packets off the queues and populate an output queue. Minimum bandwidth guarantees corresponding to different partitions essentially establishes a preference by which a flow control mechanism arbitrates among the partition queues. For example, a flow control module, while arbitrating among the partition queues, may read more packets from partitions having a higher minimum guaranteed bandwidth relative to partitions have lower or no minimum bandwidth guarantees. For example, as disclosed in U.S. application Ser. No. 10/108,085, incorporated by reference above, the bandwidth allocated to a given partition affects the rate at which the partition is selected by an output scheduling process and therefore the length of time packets are buffered in the corresponding partition queue.
Given that the network delay components discussed above are attributable to a variety of elements outside the control of any given network device, however, the partition parameters configured by a network administrator may not achieve intended or desired levels of performance-especially during times of network congestion. For example, while a network administrator may configure a partition for a given class of traffic (e.g., VoIP) with a minimum bandwidth guarantee, load on the network device itself, or network congestion generally, may cause the latency performance of the associated traffic class(es) to fall below acceptable levels. In light of the foregoing, a need in the art exists for methods, apparatuses and systems directed to an adaptive partitioning mechanism that responds to observed latency conditions. Embodiments of the present invention substantially fulfill this need.